A network planning system enables users to create a plan for a network prior to building the network. The network planning system provides the users with graphical modeling, planning, and configuration capabilities for designing a network. The network planning system attempts to generate a network plan that routes all possible demands (e.g., traffic bandwidth requirements or traffic requirements) of a network using a minimum amount of equipment, such as network devices, line modules, or the like. The network planning system may generate the network plan while simultaneously adhering to routing constraints associated with the network, adhering to rules associated with the network, and ensuring that the network plan is deployable (e.g., realizable).
Generating a network plan may be similar to a bin packing problem or a non-deterministic polynomial-time (NP)-hard problem. In a bin packing problem, objects of different volumes may be packed into a finite number of bins or containers, each of a particular volume, in a way that minimizes the number of bins used. A problem “H” may be considered a NP-hard problem when every problem “L” in non-deterministic polynomial-time can be reduced in polynomial time to problem “H.” A bin packing problem may be solved using a bin-packing algorithm, such as, for example, two-dimensional packing, linear packing, packing by weight, packing by cost, or the like.